package offer.nowcoder.array;

import java.util.*;

/**
 * @author DengYuan2
 * @create 2021-03-14 20:02
 */
public class NC93 {
    public static void main(String[] args) {
        int[][] arr ={
                {1,1,1},
                {1,2,2},
                {1,3,2},
                {2,1},
                {1,4,4},
                {2,2}
        };
        NC93 n = new NC93();
        int[] res = n.LRU(arr, 3);
        System.out.println(Arrays.toString(res));
    }


    public int[] LRU(int[][] operators, int k) {
        LinkedHashMap<Integer, Integer> map = new LinkedHashMap<Integer, Integer>();
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < operators.length; i++) {
            int oper = operators[i][0];
            int key = operators[i][1];
            //放入操作
            if (oper == 1) {
                if (map.size() < k) {
                    map.put(key, operators[i][2]);
                } else {
                    //删除第一个元素，即最久远的元素
                    Iterator<Integer> iterator = map.keySet().iterator();
                    map.remove(iterator.next());
                    map.put(key, operators[i][2]);
                }
            } else {
                if (map.containsKey(key)) {
                    int val = map.get(key);
                    list.add(val);
                    //删除该元素并将其放到最后面
                    map.remove(key);
                    map.put(key, val);
                } else {
                    list.add(-1);
                }

            }

        }
        int len = list.size();
        int[] res = new int[len];
        int idx = 0;
        for (int num : list) {
            res[idx++] = num;
        }
        return res;
    }


}
